原始题目：剑指 Offer 64. 求1+2+…+n (opens new window)

解题思路：

通过递归来实现循环的效果，通过递归函数的返回值来决定要不要继续递归。

代码：

class Solution {
    int ans = 0;

    public int sumNums(int n) {
        sum(n);
        return ans;
    }

    private boolean sum(int n) {
        ans += n;
        return n > 0 && sum(n - 1);
    }
}

复杂度分析

• 时间复杂度$O(N)$：$N$ 为输入参数，需要进行 $N$ 次递归，每次递归的运算使用 $O(1)$ 的时间。
• 空间复杂度$O(N)$：需要进行 $N$ 次递归，占用 $O(N)$ 的栈空间。